The present invention relates to secret keeping in the case where a processor requests another processor to solve a problem and thereby obtains a solution of the problem.
For example, in financial business, it is necessary to conduct enterprise ranking, i.e., estimating enterprises having a high possibility of bankruptcy and enterprises having a low possibility of bankruptcy, in order to conduct risk management in finance for enterprises.
As one method therefor, a method utilizing an optimization problem has been proposed (see, for example, Hiroshi Konno, “Measurement and management of market risk/credit risk using mathematical programming”, the 2000 fourth OR seminar text, Operations Research Society of JAPAN).
This method includes the steps of (1) plotting enterprises which are subjects of finance on a high-dimensional space according to financial indices such as the self capital ratio and cash flow; (2) calculating such a hyperplane that can discriminate bankrupt enterprises from non-bankrupt enterprises most accurately (i.e., with minimum discrimination errors) in the space on the basis of past actual results; and (3) ranking the subject enterprises on the basis of distances from the hyperplane.
As a matter of fact, information concerning the optimization problems includes secret information affecting the basis of business, such as delivery points and delivery routes in the distribution industry, and contents of bond portfolios, financial indices of financed enterprises, ranking information of financed enterprises, personal information for credit card examination, and results of examination in financial business.
Therefore, if there is a fear of leaking of these kinds of information by requesting the ASP to conduct optimization, requesting is hardly conceivable. For putting the ASP concerning solving of optimization problems to practical use, therefore, there is needed a method capable of ensuring sufficient secret keeping with respect to both information of optimization problems to be solved and information of obtained solutions.
As the method for this, a method proposed in, for example, U.S. Pat. No. 5,963,731 has mainly been used heretofore.
In the industry fields such as distribution industry and financial business, it is necessary to solve various optimization problems including optimization of delivery routes of a truck and optimization of bond portfolios.
For example, in optimization of the truck delivery route, a plurality of delivery points are given on a map, and there is found such a route that the truck passes each of the delivery points once and the length is minimized. As a result, the traveling distance can be shortened as far as possible, and the expense required for transport can be minimized.
As an example, it is now assumed that 100 delivery points are given on a plane. FIG. 2 shows a delivery route obtained when the truck goes around to all of the delivery points in a random order. FIG. 3 shows its optimum delivery route.
As compared with the delivery route in the random order, the traveling distance is reduced to a fraction in the optimum delivery route. The transport expense can be saved remarkably.
Furthermore, for example, in optimization of bond portfolios, there is given such a condition that a fund of a constant amount is given and dispersions of expected earning rates and earning rates are given with respect to bonds such as stocks, government bonds, and debentures. Under this condition, there is solved a problem as to how to dispersedly invest a fund to bonds in order to minimize the total risk, i.e., dispersion of earning rates while keeping the total earning rate constant.
These problems can be formulated mathematically as a linear programming problem, a quadratic programming problem, or a mixed integer programming problem.
A linear programming problem is a problem of finding x which minimizes an objective function ctx under an equality constraint Ax=b and an inequality constraint x≧0.
Here, x is an n-dimensional vector of an unknown quantity. A is a constant matrix having m rows and n columns, and c is an n-dimensional constant vector. Furthermore, x≧0 represents a condition that all elements of x are not negative, and ctx represents an inner product of a vector c and a vector x.
A quadratic programming problem is an optimization problem obtained by changing an objective function of a linear programming problem into a quadratic function ctx+xtBx.
Here, B is a constant non-negative definite matrix having n rows and n columns.
A mixed integer programming problem is an optimization problem obtained by imposing an integer condition on partial components of a vector x of an unknown quantity in a linear programming problem.
The above described optimization of the delivery route of the truck becomes a mixed integer programming problem, because the condition that the truck passes each of the delivery points once can be represented by an equality constraint Ax=b with an integer condition and the length of the delivery route can be represented by a linear function ctx.
The above described optimization of bond portfolios becomes a quadratic programming problem, because the conditions that the amount of the fund is constant and the earning rate is constant can be represented by an equality constraint Ax=b and an objective function for minimizing the risk can be represented by a quadratic function xtBx.